<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var searchInsert = function (nums, target) {
        //最简单的方式肯定是直接遍历
        //用二分的方式
        let left = 0;
        let right = nums.length;
        while (left <= right) {
          let middle = parseInt((left + right) / 2);
          if (nums[middle] == target) {
            //因为没有重复元素，如果找到相同的，那么它的下标就是要插入的下标
            return middle;
          } else if (nums[middle] < target) {
            left = middle + 1;
          } else {
            right = middle;
          }
        }
        //因为left==right是成立的
        /* 
        第一次left=0 right=6 middle=3  6>4 所以right=3
        第二次left=0  right=3 middle=1 3<4 所以left=middle+1=1
        第三次left=1 right=3 middle=2 5>4 所以right=middle=2
        第四次left=1 right=2 middle=1 3<4 所以left=middle+1=2  此后推出while循环 left==right
        所以可以选择返回left也可以选择返回right
        */
       
        return left;
      };
      searchInsert([1, 3, 5, 6, 8, 10], 4);
    </script>
  </body>
</html>
